package com.leo.datastruct.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树
 * @author xuexiaolei
 * @version 2018年02月04日
 */
public class BSTree<T extends Comparable<T>> {
    private BSNode<T> mRoot;    //根节点

    class BSNode<T extends Comparable<T>>{
        T key;              //存储的值
        BSNode<T> left;     //左孩子
        BSNode<T> right;    //右孩子
        BSNode<T> parent;   //父节点

        public BSNode() {}

        public BSNode(T key) {
            this.key = key;
        }

        public BSNode(T key, BSNode<T> left, BSNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }

        public BSNode(T key, BSNode<T> left, BSNode<T> right, BSNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    /**
     * 访问节点的方法，可以自定义
     * @param node
     */
    public void visitNode(BSNode<T> node){
        System.out.print(node.key + " ");
    }

    //*****************************遍历 start*************************************************
    /**
     * 先序遍历——递归方式
     * @param tree
     */
    public void preOrder(BSNode<T> tree){
        if (tree != null){
            visitNode(tree);
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
    /**
     * 先序遍历——非递归方式
     * @param tree
     */
    public void preOrder2(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        if (tree != null){
            stack.push(tree);
            while (!stack.isEmpty()){
                tree = stack.pop();
                visitNode(tree);
                if (tree.left !=null ){
                    stack.push(tree.left);
                }
                if (tree.right !=null ){
                    stack.push(tree.right);
                }
            }
        }
    }
    /**
     * 先序遍历——非递归方式
     * @param tree
     */
    public void preOrder3(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        BSNode<T> node = tree;
        while (node != null || !stack.isEmpty()){
            while (node != null){
                visitNode(node);
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }
        }
    }
    public void preOrder(){
        preOrder(mRoot);
    }

    /**
     * 中序遍历——递归方式
     * @param tree
     */
    public void midOrder(BSNode<T> tree){
        if (tree != null){
            midOrder(tree.left);
            visitNode(tree);
            midOrder(tree.right);
        }
    }
    /**
     * 中序遍历——非递归方式
     * @param tree
     */
    public void midOrder2(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        while (tree != null){
            while (tree != null){
                // 当前节点右子入栈
                if (tree.right != null){ stack.push(tree.right); }
                // 当前节点入栈
                stack.push(tree);
                tree = tree.left;
            }
            tree = stack.pop();
            while (!stack.isEmpty() && tree.right==null){
                visitNode(tree);
                tree = stack.pop();
            }
            visitNode(tree);
            if (!stack.isEmpty()){
                tree = stack.pop();
            }else {
                tree = null;
            }
        }
    }
    /**
     * 中序遍历——非递归方式
     * @param tree
     */
    public void midOrder3(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        BSNode<T> node = tree;
        while (node!=null || !stack.isEmpty()){
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()){
                node = stack.pop();
                visitNode(node);
                node = node.right;
            }
        }
    }
    public void midOrder(){
        midOrder(mRoot);
    }

    /**
     * 后序遍历——递归方式
     * @param tree
     */
    public void postOrder(BSNode<T> tree){
        if (tree != null){
            postOrder(tree.left);
            postOrder(tree.right);
            visitNode(tree);
        }
    }
    /**
     * 后序遍历——非递归方式 单栈法
     * @param tree
     */
    public void postOrder2(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        BSNode<T> node = tree;
        BSNode<T> pre = tree;  //需要记录已经访问过的节点
        while (node!=null || !stack.isEmpty()){
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()){
                BSNode<T> temp = stack.peek().right;
                if (temp==null || temp == pre){
                    node = stack.pop();
                    visitNode(node);
                    pre = node;
                    node = null;
                }else {
                    node = temp;
                }
            }
        }
    }
    /**
     * 后序遍历——非递归方式 双栈法
     * @param tree
     */
    public void postOrder3(BSNode<T> tree){
        //使用栈的方式来实现非递归遍历。此处使用的Deque理解为栈的一种实现即可
        Deque<BSNode<T>> stack = new LinkedList<>();
        Deque<BSNode<T>> temp = new LinkedList<>();
        BSNode<T> node = tree;
        while (node!=null || !stack.isEmpty()){
            while (node!=null){
                temp.push(node);
                stack.push(node);
                node = node.right;
            }
            if (!stack.isEmpty()){
                node =  stack.pop();
                node = node.right;
            }
        }
        while (!temp.isEmpty()){
            node = temp.pop();
            visitNode(node);
        }
    }

    /**
     * 双栈法，更好理解的写法
     * @param node
     */
    public void postOrder4(BSNode node){
        LinkedList<BSNode> stack = new LinkedList();
        LinkedList<BSNode> temp = new LinkedList();
        if (node!=null) {stack.push(node);}
        while (!stack.isEmpty()){
            BSNode pop = stack.pop();
            temp.push(pop);
            if (pop.left!=null){ stack.push(pop.left); }
            if (pop.right!=null){ stack.push(pop.right); }
        }
        while (!temp.isEmpty()){ visitNode(temp.pop()); }
    }

    public void postOrder(){
        postOrder(mRoot);
    }

    /**
     * 层次遍历--借用队列来实现
     * @param tree
     */
    public void levelIterator(BSNode<T> tree){
        if (tree == null){ return;}
        Queue<BSNode<T>> queue = new LinkedList<>();
        BSNode<T> current = null;
        queue.offer(tree);
        while (!queue.isEmpty()){
            current = queue.poll();
            visitNode(current);
            if (current.left != null){ queue.offer(current.left); }
            if (current.right != null){ queue.offer(current.right); }
        }
    }
    public void levelIterator(){
        levelIterator(mRoot);
    }
    //*****************************遍历 end*************************************************

    //*****************************查找 start*************************************************

    /**
     * 查找二叉树中值为key的节点--递归
     * @param tree
     * @param key
     * @return
     */
    public BSNode<T> search(BSNode<T> tree, T key){
        if (tree == null){ return null; }
        int cmp = key.compareTo(tree.key);
        if (cmp < 0){
            return search(tree.left, key);
        }else if (cmp > 0){
            return search(tree.right, key);
        }else {
            return tree;
        }
    }

    //*****************************查找 end*************************************************

    //*****************************最值 start*************************************************

    /**
     * 找树中的最大值节点
     * @param tree
     * @return
     */
    public BSNode<T> max(BSNode<T> tree){
        if (tree == null){ return null; }
        while (tree.right != null){
            tree = tree.right;
        }
        return tree;
    }

    public T max(){
        BSNode<T> max = max(mRoot);
        if (max != null){
            return max.key;
        }else {
            return null;
        }
    }

    /**
     * 找树中的最小值节点
     * @param tree
     * @return
     */
    public BSNode<T> min(BSNode<T> tree){
        if (tree == null){ return null; }
        while (tree.left != null){
            tree = tree.left;
        }
        return tree;
    }

    public T min(){
        BSNode<T> min = min(mRoot);
        if (min != null){
            return min.key;
        }else {
            return null;
        }
    }

    //*****************************最值 end*************************************************

    //*****************************插入 start*************************************************

    /**
     * 将节点插入二叉树
     * @param tree
     * @param key
     */
    public void insert(BSTree<T> tree, T key){
        BSNode<T> insert = new BSNode<>(key);
        BSNode<T> parent = null;       //插入节点的父节点
        BSNode<T> temp = tree.mRoot;
        int cmp;

        while (temp != null){
            parent = temp;
            cmp = key.compareTo(temp.key);
            if (cmp < 0){
                temp = temp.left;
            }else if (cmp > 0){
                temp = temp.right;
            }else {
                throw new RuntimeException("不允许插入相同值");
            }
        }

        insert.parent = parent;
        if (parent == null){
            tree.mRoot = insert;
        }else {
            cmp = key.compareTo(parent.key);
            if (cmp < 0){
                parent.left = insert;
            }else {
                parent.right = insert;
            }
        }
    }
    //*****************************插入 end*************************************************
    //*****************************删除 start*************************************************

    /**
     * 删除值为key的节点并返回这个节点
     * @param tree
     * @param key
     */
    public BSNode<T> remove(BSTree<T> tree, T key){
        //先查找这个值为key的节点
        BSNode<T> search = search(tree.mRoot, key);
        if (search!=null){
            //如果找到节点的左右子树均不为空
            //那就找到他的左子树的最大值，也就是它的前驱节点，然后替换他们
            //接下来只需删除前驱节点即可，而且，前驱节点必然最多只有一个子树
            if (search.left != null && search.right != null){
                BSNode<T> max = max(search.left);//找到左子树的最大值
                search.key = max.key;
                max.key = key;
                search = max;
            }

            boolean isLeftChild = true;//判断查找的节点是否是父节点的左孩子
            BSNode<T> searchParent = search.parent;
            {//更正isLeftChild的值
                if (searchParent != null){
                    if (searchParent.left != search){ isLeftChild = false; }
                }
            }
            //查找成功
            if (search.left ==null && search.right==null){
                //左右节点均不存在的情况
                if (search == tree.mRoot){
                    tree.mRoot = null;
                }else if (isLeftChild){
                    searchParent.left = null;
                }else {
                    searchParent.right = null;
                }
            }else if (search.right == null) {
                if (search == tree.mRoot) {
                    tree.mRoot = search.left;
                } else if (isLeftChild) {
                    searchParent.left = search.left;
                } else {
                    searchParent.right = search.left;
                }
            } else if (search.left == null) {
                if (search == tree.mRoot) {
                    tree.mRoot = search.right;
                } else if (isLeftChild) {
                    searchParent.left = search.right;
                } else {
                    searchParent.right = search.right;
                }
            }
            return search;
        }else {
            //未查找到
            return null;
        }
    }
    //*****************************删除 end*************************************************

    /**
     * 打印"二叉查找树"
     * @param tree
     * @param key           节点的键值
     * @param direction     0，表示该节点是根节点;-1，表示该节点是它的父结点的左孩子;1，表示该节点是它的父结点的右孩子。
     */
    private void print(BSNode<T> tree, T key, int direction) {

        if(tree != null) {

            if(direction==0){    // tree是根节点
                System.out.printf("%2d is root\n", tree.key);
            } else {                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
            }

            print(tree.left, tree.key, -1);
            print(tree.right,tree.key,  1);
        }
    }



    public BSNode buildTreeHelper(int[] inorder,int is,int ie,int[] preorder,int ps) {
        if(is>ie || ps >= preorder.length) {return null;}
        //首先从inorder中确定第一个，然后既可以划分左右子树
        BSNode root = new BSNode(preorder[ps]);
        int rootAtIn = is;
        while(inorder[rootAtIn] != (int)root.key) {rootAtIn ++;} //查找本节点的位置
        //拆分成两个子问题
        root.left =  buildTreeHelper(inorder,is,rootAtIn - 1,preorder,ps+1);
        root.right = buildTreeHelper(inorder,rootAtIn+1,ie,preorder,ps+rootAtIn - is + 1);
        return root;
    }
    public BSNode buildTree(int[] preorder, int[] inorder) {//先序+中序恢复二叉树
        return buildTreeHelper(inorder,0,inorder.length-1,preorder,0);

    }

    public void print() {
        if (mRoot != null){
            print(mRoot, mRoot.key, 0);
        }
    }

    public static void main(String[] args) {
        BSTree<Integer> t = new BSTree<>();
        int[] arr = new int[]{1,5,4,3,2,6};
        for (int i = 0; i < arr.length; i++) {
            t.insert(t, arr[i]);
        }
        System.out.print("\n== 前序遍历: ");
        t.preOrder();
        System.out.print("\n== 中序遍历: ");
        t.midOrder();
        System.out.print("\n== 后序遍历: ");
        t.postOrder();
        System.out.print("\n== 层次遍历: ");
        t.levelIterator();

        System.out.println();
        System.out.println("== 最小值: "+ t.min());
        System.out.println("== 最大值: "+ t.max());

//        t.remove(t, 1);
//        t.remove(t, 5);
        t.remove(t, 6);
        t.print();


    }
}
